package myrbtree

import (
	"fmt"
)

const (
	// 结点-- 红黑两色
	RED   bool = true
	BLACK bool = false
)

// 结点
type Node struct {
	value               int64
	color               bool
	left, right, parent *Node
}

// 新结点 为 红色结点
// 红色在父结点为黑色结点时，红黑树的黑色平衡没被破坏
// 不需要自平衡操作
func NewNode(value int64) *Node {
	return &Node{value, RED, nil, nil, nil}
}

// 树的结构
type RBTree struct {
	root *Node
}

func NewTree(node *Node) *RBTree {
	node.color = BLACK
	return &RBTree{node}
}

func (rbtree *RBTree) GetTreeRoot() *Node {
	root := rbtree.root
	return root
}

// 获取父级结点的父级结点
func (rbnode *Node) getGrandParent() *Node {
	if rbnode.parent == nil {
		return nil
	}

	if rbnode.parent.parent == nil {
		return nil
	}

	return rbnode.parent.parent
}

// 获取兄弟结点
func (rbnode *Node) getSibling() *Node {
	if rbnode.parent == nil {
		return nil
	}

	if rbnode.parent.left != nil && rbnode.parent.left == rbnode {
		return rbnode.parent.right
	}

	return rbnode.parent.left
}

// 父结点的兄弟结点
func (rbnode *Node) getUncle() *Node {
	if rbnode.parent == nil {
		return nil
	}
	if rbnode.parent.parent == nil {
		return nil
	}

	if rbnode.parent.parent.left == rbnode.parent {
		return rbnode.parent.parent.right
	}

	return rbnode.parent.parent.left
}

func isRed(node *Node) bool {
	if node != nil && node.color == RED {
		return true
	}
	return false
}

func isBlack(node *Node) bool {
	if node != nil && node.color == BLACK {
		return true
	}
	return false
}

// 查找 结点的前驱结点 在左子树查找
// 左子树中最大值结点
func findPredecessor(node *Node) *Node {
	if node == nil {
		return node
	}

	var t *Node
	t = node.left
	for {
		if t.right == nil {
			break
		}

		t = t.right
	}

	return t
}

// 查找 结点的后继结点 在右子树查找
func findSuccessor(node *Node) *Node {
	if node == nil {
		return node
	}

	var t *Node
	t = node.right
	for {
		if t.left == nil {
			break
		}

		t = t.left
	}

	return t
}

// 先序遍历 根 左 右
func (node *Node) ListNode() {
	if node != nil {
		node.left.ListNode()
		fmt.Println(node.value, node.color, node.left, node.right, node.parent)
		node.right.ListNode()
	}
}

// 根据data查找对应的点
func (rbtree *RBTree) Search(data int64) *Node {
	node := rbtree.root
	for {
		if node != nil {
			if node.value > data {
				node = node.left
			} else if node.value < data {
				node = node.right
			} else {
				return node
			}
		} else {
			return nil
		}
	}
}

// 左旋
/*
*        G
*     S       P
*           lp  rp
 */
// node是旋转点(假设是G结点)
func (rbtree *RBTree) rotateLeft(node *Node) {
	// 旋转点的右子结点(P)
	rnode := node.right
	// 右子结点的左子结点(lp变成G的右子结点)
	node.right = rnode.left
	// 设置lp的父结点为G
	if rnode.left != nil {
		rnode.left.parent = node
	}
	// 设置P的父结点
	rnode.parent = node.parent
	// 祖父结点的设定
	if node.parent == nil {
		rbtree.root = rnode
	} else {
		if node.parent.left == node {
			node.parent.left = rnode
		} else {
			node.parent.right = rnode
		}
	}
	// 将P结点的左子结点设为G
	rnode.left = node
	// G结点的父结点设为P
	node.parent = rnode
}

// 右旋
/*
*        G
*     P       S
*  lp  rp
 */
// node是旋转点(假设是G结点)
func (rbtree *RBTree) rotateRight(node *Node) {
	// 旋转点的左子结点P
	lnode := node.left
	// 左子结点P的右子结点rp 设为G的左子结点
	node.left = lnode.right
	// 将rp的父结点设为G结点
	if lnode.right != nil {
		lnode.right.parent = node
	}
	// 设置P的父结点 为 G的父结点
	lnode.parent = node.parent
	// 祖父结点设定
	if node.parent == nil {
		rbtree.root = lnode
	} else {
		if node.parent.right == node {
			node.parent.right = lnode
		} else {
			node.parent.left = lnode
		}
	}
	// P结点的右子结点设为G
	lnode.right = node
	// G的父结点设为P
	node.parent = lnode
}

// 插入结点
// pnode 是父结点
func (rbtree *RBTree) InsertNode(pnode *Node, data int64) {
	if pnode == nil {
		if rbtree.root == nil {
			tmpnode := NewNode(data)
			tmpnode.color = BLACK
			rbtree.root =tmpnode
			return
		}

		pnode = rbtree.root
	}

	// 插入 左子树
	// 2. 插入结点的Key已存在
	// 把I设为当前结点的颜色
	// 更新当前结点的值为插入结点的值
	if pnode.value >= data {
		// 插入数据 不大于 父节点，则 插入左子结点
		if pnode.left != nil {
			rbtree.InsertNode(pnode.left, data)
		} else {
			tmpnode := NewNode(data)
			tmpnode.parent = pnode
			pnode.left = tmpnode
			rbtree.insertAdjustment(tmpnode)
		}
	} else { // 插入 右子树
		// 插入数据大于父节点，插入右子结点
		if pnode.right != nil {
			rbtree.InsertNode(pnode.right, data)
		} else {
			tmpnode := NewNode(data)
			tmpnode.parent = pnode
			pnode.right = tmpnode
			rbtree.insertAdjustment(tmpnode)
		}
	}
}

func (rbtree *RBTree) insertAdjustment(node *Node) {
	// 1. 红黑树为空树
	if node.parent == nil {
		// 检查 插入结点 若没有父节点，则该节点为root
		rbtree.root = node
		// 设置 根结点 为black
		rbtree.root.color = BLACK
		return
	}

	// 4. 插入结点的父结点为红结点
	// 父结点是黑色则直接添加，红色则进行处理
	// 父结点是红色，则该父结点不是根结点
	if node.parent.color == RED {
		uncle := node.getUncle()
		// 叔结点存在且为红色，祖父结点肯定为黑结点
		// 因为不可以同时存在两个相连的红结点
		// 插入子树的红黑层数是：黑红红，需要改为：红黑红
		if uncle != nil && uncle.color == RED {
			// 父结点和叔结点 改为黑色
			node.parent.color = BLACK
			uncle.color = BLACK
			// 祖父结点 改为 红色
			if node.getGrandParent() != nil {
				node.getGrandParent().color = RED
				// 检查 祖父结点
				rbtree.insertAdjustment(node.getGrandParent())
			}
		} else {
			// 父结点红色，父结点的兄弟结点不存在或者为黑色时
			isleft := node == node.parent.left
			gpLeft := node.getGrandParent()
			if gpLeft != nil {
				gpLeft = gpLeft.left
			}

			isparentleft := node.parent == gpLeft
			// 左(父结点是祖父结点的左子结点)-左(当前结点是父结点的左子结点)
			if isparentleft && isleft { // LL
				// 父结点 设为 黑色
				node.parent.color = BLACK
				// 祖父结点 设为 红色
				grandParent := node.getGrandParent()
				if grandParent != nil {
					grandParent.color = RED
					// 把 祖父结点 设为插入结点，右旋
					rbtree.rotateRight(grandParent)
				}
			} else if isparentleft && !isleft { // LR
				// 左(父结点是祖父结点的左子结点)-右(当前结点是父结点的右子结点)
				rbtree.rotateLeft(node.parent)
				rbtree.rotateRight(node.parent)

				node.color = BLACK
				node.left.color = RED
				node.right.color = RED
			} else if !isparentleft && !isleft { // RR
				// 右(父结点是祖父结点的右子结点)-右(当前结点是父结点的右子结点)
				node.parent.color = BLACK
				if node.getGrandParent() != nil {
					node.parent.parent.color = RED
					rbtree.rotateLeft(node.parent.parent)
				}
			} else if !isparentleft && isleft { // RL
				// 右(父结点是祖父结点的右子结点)-左(当前结点是父结点的左子结点)
				rbtree.rotateRight(node.parent)
				rbtree.rotateLeft(node.parent)
				node.color = BLACK
				node.left.color = RED
				node.right.color = RED
			}
		}
	}
	// 3. 插入结点的父结点为黑结点
	// 由于插入的结点是红色的，当插入结点的黑色时，
	// 并不会影响红黑树的平衡，直接插入即可，无需做自平衡。
}

func (rbtree *RBTree) DeleteChild(data int64) bool {
	// 先找到要删除的结点
	node := rbtree.Search(data)
	if node == nil {
		return false
	}

	// 正是要删除的结点
	rbtree.deleteNode(node)
	return true
}

// 删除结点
func (rbtree *RBTree) deleteNode(node *Node) {
	// 用于记录替换结点的子结点和父结点
	var child, parent *Node
	// 记录 替换结点的颜色
	var color bool
	// 先处理 有2个子结点的点
	if node.left != nil && node.right != nil {
		// 查找替代结点，后继结点
		repalce := findSuccessor(node)
		// 用替换结点 替换 删除结点
		if node.parent != nil {
			if node.parent.left == node {
				node.parent.left = repalce
			} else {
				node.parent.right = repalce
			}
		} else {
			// 根结点的场合
			rbtree.root = repalce
		}
		// 记录替换结点的父和子结点
		parent = repalce.parent
		child = repalce.right
		color = repalce.color

		// 若替换结点的父结点 就是 删除结点
		if parent == node {
			parent = repalce
		} else {
			// 子结点不为空 必定是替换结点的右子结点
			if child != nil {
				child.parent = parent
			}
			parent.left = child
			// 用替换结点变为删除结点
			repalce.right = node.right
			node.right.parent = repalce
		}

		repalce.parent = node.parent
		repalce.color = node.color
		repalce.left = node.left
		node.left.parent = repalce

		// 若替换结点是黑色
		if color == BLACK {
			// 调整 红黑平衡
			rbtree.deleteAdjustment(child, parent)
		}

		// 红色时直接删除结点
		node = nil
	} else {
		// 两个都为空或其中一个为空
		if node.left == nil || node.right == nil {
			rbtree.deleteOne(node)
		}
	}
}

func (rbtree *RBTree) deleteOne(node *Node) {
	var child *Node
	if node.left == nil {
		child = node.right
	} else {
		child = node.left
	}

	if node.parent == nil && node.left == nil && node.right == nil {
		node = nil
		rbtree.root = nil
		return
	}
	// 删除结点是根结点时
	if node.parent == nil {
		node = nil
		child.parent = nil
		child.color = BLACK
		rbtree.root = child
		return
	}

	// 删除结点是红色 直接使用子结点替换
	if node.color == RED {
		if node.parent.left == node {
			node.parent.left = child
		} else {
			node.parent.right = child
		}

		if child != nil {
			child.parent = node.parent
		}
		node = nil
		return
	}

	// 删除结点是黑色，且子结点是红色
	if child != nil && child.color == RED {
		// 将子结点变成黑色
		child.color = BLACK
		if node.parent.left == node {
			node.parent.left = child
		} else {
			node.parent.right = child
		}
		child.parent = node.parent
		// 删除结点
		node = nil
		return
	}

	// 删除结点是黑色，且无子结点
	if child == nil {
		parent := node.parent
		// 调整 红黑平衡
		rbtree.deleteAdjustment(child, parent)
	}
	// 删除结点的关联关系
	if node.parent.left == node {
		node.parent.left = nil
	} else {
		node.parent.right = nil
	}

	node = nil

}

// 删除调整，对新的关系进行调整
// 也是场景的转换
// node是 替换结点 的 右子结点
// parent是 替换结点 的 父结点
// 此时 node是parent的子结点
func (rbtree *RBTree) deleteAdjustment(node *Node, parent *Node) {
	var other *Node
	if (node == nil || isBlack(node)) && node != rbtree.root {
		if parent.left == node { // 是左子结点的场合
			// node的兄弟结点
			other = parent.right
			// 1. 兄弟结点是红色
			if isRed(other) {
				// 将兄弟结点变成黑色，父结点变成红色
				other.color = BLACK
				parent.color = RED
				// 左旋P结点
				rbtree.rotateLeft(parent)
				other = parent.right
			}
			// 2. 兄弟结点是黑色，且其子结点也是黑色
			if (other.left == nil || isBlack(other.left)) && (other.right == nil || isBlack(other.right)) {
				// 兄弟结点变成红色
				other.color = RED
				// 将父结点设为新的调整点
				node = parent
				if node == nil {
					parent = node.parent
				} else {
					parent = nil
				}
			} else {
				// 3. 兄弟结点的右子结点是黑色
				if other.right == nil || isBlack(other.right) {
					// LS 设为黑色，兄弟结点设为红色，再右旋兄弟结点
					if other.left != nil {
						other.left.color = BLACK
					}
					other.color = RED
					rbtree.rotateRight(other)
					other = parent.right
				}

				// 4. 兄弟结点的右子结点是红色
				// 父结点与兄弟结点互换颜色
				if parent == nil {
					other.color = BLACK
				} else {
					other.color = parent.color
				}
				parent.color = BLACK
				if other.right != nil {
					other.right.color = BLACK
				}
				// 左旋父结点
				rbtree.rotateLeft(parent)
				node = rbtree.root
				return
			}
		} else { // 右子结点的场合
			other = parent.left
			if isRed(other) {
				// 1. node的兄弟other是红色的
				other.color = BLACK
				parent.color = RED
				rbtree.rotateRight(parent)
				other = parent.left
			}

			if (other.left == nil || isBlack(other.left)) && (other.right == nil || isBlack(other.right)) {
				// 2: node的兄弟other是黑色，且other的俩个子节点都是黑色的
				other.color = RED
				node = parent
				if node == nil {
					parent = node.parent
				} else {
					parent = nil
				}
			} else {

				if other.left == nil || isBlack(other.left) {
					// 3: node的兄弟other是黑色的，并且other的左子节点是红色，右子节点为黑色。
					if other.right != nil {
						other.right.color = BLACK
					}
					other.color = RED
					rbtree.rotateLeft(other)
					other = parent.left
				}

				// 4: node的兄弟other是黑色的；并且other的左子节点是红色的，右子节点任意颜色
				if parent == nil {
					other.color = BLACK
				} else {
					other.color = parent.color
				}
				parent.color = BLACK
				if other.left != nil {
					other.left.color = BLACK
				}
				rbtree.rotateRight(parent)
				node = rbtree.root
				return
			}
		}
		rbtree.deleteAdjustment(node, parent)
	}
}

func MyTree() {
	var nodes = [13]int64{85, 15, 70, 20, 60, 30, 50, 65, 80, 90, 40, 5, 55}
	root := NewNode(10)
	rbtree := NewTree(root)
	
	lg := len(nodes)
	for i := 0; i < lg; i++ {
		rbtree.InsertNode(nil, nodes[i])
	}

	rbtree.DeleteChild(30)
	treeRoot := rbtree.GetTreeRoot()
	treeRoot.ListNode()
	fmt.Println(*treeRoot)
}
